package leetcode_堆;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 前 K 个高频元素
 * 算法: 堆、桶排序
 *
 * @author yezh
 * @date 2025/1/20 16:10
 */
public class _347 {

    public int[] topKFrequent(int[] nums, int k) {
        int[] ans = new int[k];
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, Comparator.comparingInt(a -> map.getOrDefault(a, 0)));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k) queue.offer(entry.getKey());
            else if (map.getOrDefault(queue.peek(), 0) < entry.getValue()) {
                queue.poll();
                queue.offer(entry.getKey());
            }
        }
        while (!queue.isEmpty())
            ans[--k] = queue.poll();
        return ans;
    }

}
